package problems.daily;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

/**
 * 2258. 逃离火灾
 *
 * @author dubulingbo, 2023/11/9 20:59.
 */
public class DT2258 {
    final int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

    /**
     * 二分 + bfs
     */
    public int maximumMinutes(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        // 记录火到每个格子的时间
        int[][] arriveTime = new int[n][m];

        calcArriveTime(arriveTime, grid);

        // 二分计算最大滞留时间
        int left = 0, right = m * n;
        while (left < right) {
            int mid = (left + right) / 2;
            // 在滞留 mid 分钟后，是否还能安全到达出口
            boolean pass = check(grid, arriveTime, mid);

            if (pass) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return left >= m * n ? -1 : left;
    }

    private boolean check(int[][] grid, int[][] arriveTime, int stayTime) {
        int m = grid.length;
        int n = grid[0].length;

        boolean[][] vis = new boolean[m][n];
        Queue<int[]> que = new ArrayDeque<>();

        que.offer(new int[] {0, 0, stayTime});
        vis[0][0] = true;

        while (!que.isEmpty()) {
            for (int sz = que.size(); sz > 0; --sz) {
                int[] c = que.poll();
                for (int i = 0; i < dir.length; ++i) {
                    int x = c[0] + dir[i][0];
                    int y = c[1] + dir[i][1];
                    if (x < 0 || x >= m || y < 0 || y >= n) continue;
                    if (x == m - 1 && y == n - 1) return arriveTime[x][y] >= c[2] + 1;
                    // TODO 这里是从【stayTime + 1】开始移动的，所以是严格大于表示能安全通过
                    if (!vis[x][y] && grid[x][y] == 0 && arriveTime[x][y] > c[2] + 1) {
                        vis[x][y] = true;
                        que.offer(new int[] {x, y, c[2] + 1});
                    }
                }
            }
        }
        return false;
    }

    /**
     * BFS 计算火势到达时间
     */
    private void calcArriveTime(int[][] arriveTime, int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;

        // 初始化为无穷大
        for (int i = 0; i < n; ++i) {
            Arrays.fill(arriveTime[i], Integer.MAX_VALUE);
        }

        Queue<int[]> que = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    que.offer(new int[]{i, j});
                    arriveTime[i][j] = 0;
                }
            }
        }

        while (!que.isEmpty()) {
            for (int i = que.size(); i > 0; --i) {
                int[] cur = que.poll();
                for (int k = 0; k < dir.length; ++k) {
                    int x = cur[0] + dir[k][0];
                    int y = cur[1] + dir[k][1];
                    if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 0 && arriveTime[x][y] == Integer.MAX_VALUE) {
                        arriveTime[x][y] = arriveTime[cur[0]][cur[1]] + 1;
                        que.offer(new int[]{x, y});
                    }
                }
            }
        }

    }
}
